The present invention relates to a Viterbi detector for maximum-likelihood decoding of a reproduced signal from a recording medium such as a magnetic disk, a magneto-optical disk and an optical disk.
Recently, recording media such as CD (Compact Disk) and DVD (Digital Versatile Disk) have attracted attention because of their ability to semi-permanently store the recorded data. Encoding technology such as EFM (Eight to Fourteen Modulation) and 8/16 modulation as well as signal processing technology called PRML (Partial Response Maximum Likelihood) are used to improve the data recording density and data reproducing capability of the CD and DVD.
FIG. 6 schematically shows a PRML-based DVD recording/reproducing system. For convenience, it is herein assumed that the system of FIG. 6 uses PR (Partial Response) (3, 4, 4, 3).
Referring to FIG. 6, an 8/16 modulator 1 modulates 8-bit original input data into a 16-bit modulation code defined by a modulation table. A basic modulation rule is that the number of successive zeros (“0”) between code bits “1” and “1” is in the range of two to ten. This rule is commonly called (2, 10) RLL (Run Length Limited). A channel bit pulse train Ak resulting from NRZI (Non Return to Zero Inverted) conversion of the modulation code string is recorded on a disk 2. Provided that a channel bit width is T, the shortest pulse width of the recorded channel bit pulse train Ak is 3T and the longest pulse width is 11T according to the above modulation rule.
An optical pickup 3 reads a channel bit pulse train Bk from the disk 2 for output to an analog filter 3 as an analog reproduced signal. The analog filter 4 filters out a high frequency component from the received analog reproduced signal, and controls a signal component of a specific frequency band toward frequency characteristics of PR (3, 4, 4, 3).
The analog reproduced signal thus filtered by the analog filter 4 is applied to an analog-digital (A-D) converter 5. The A-D converter 5 converts the received analog reproduced signal into a digital signal for output to an FIR (Finite Impulse Response) filter 6, where the digital signal is further equalized toward the frequency characteristics of PR (3, 4, 4, 3). A PR (3, 4, 4, 3)-type Viterbi detector 7 receives the equalized digital signal Yk for decoding into binary reproduced data B′k. Note that, although not shown in the figure, a clock signal used in sampling in the A-D converter 5 and operation of the digital circuitry in the subsequent stage (FIR 6 and Viterbi detector 7) is produced by a frequency comparator, a phase comparator and a voltage-controlled oscillator based on the analog reproduced signal.
Hereinafter, the Viterbi detector will be described.
The Viterbi detector is known as a maximum-likelihood decoder of a convolutional code. In the system of FIG. 6, the process of obtaining the digital filter output Yk from the channel bit pulse train Bk recorded on the disk 2 can be regarded as convolutional encoding operation. As shown in FIG. 7, this convolutional encoding operation can be represented using three delay elements 20a, 20b, 20c and four multiplying elements 21a, 21b, 21c, 21d (constraint length K=4). Yk may have nine values (0, 3, 4, 6, 7, 8, 10, 11, 14) based on combination of the values Bk.
The operation conducted by the Viterbi detector 7 of FIG. 6 is opposite to the encoding operation of FIG. 7. In other words, the Viterbi detector 7 decodes the most likely channel bit pulse train, that is, reproduced data B′k, based on the states of the delay elements 20a, 20b, 20c, or combination of the states of the delay elements 20a, 20b, 20c and the digital filter output Yk.
The three delay elements 20a, 20b, 20c of FIG. 7 may have eight states (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0) and (1, 1, 1). In view of the fact that the shortest pulse width is 3T, the states (0, 1, 0), (1, 0, 1) are impossible. Therefore, the three delay elements 20a, 20b, 20c may have six states. In this case, the digital filter output Yk may have five values (0, 4, 7, 11, 14).
The six states are herein defined as follows:
S0=(0, 0, 0);
S1=(1, 0, 0);
S2=(1, 1, 0);
S3=(0, 0, 1);
S4=(0, 1, 1); and
S5=(1, 1, 1).
In this case, the channel bit pulse train Bk and the digital filter output Yk transition with time according to the state transition diagram of FIG. 8. More specifically, there are transitions from S0 to S0, S0 to S1, S1 to S2, S2 to S5, S5 to S5, S5 to S4, S4 to S3, and S3 to S0. FIG. 9 is a trellis diagram based on the state transition of FIG. 8.
FIG. 10 shows an example of the Viterbi detector 7 for decoding the reproduced data based on the state transition of FIG. 8. The Viterbi detector 7 of FIG. 10 includes a branch metric calculating section 50, an ACS (Add-Compare-Select) operation section 51, a path memory 52 and a maximum-likelihood determination section 53.
The branch metric calculating section 50 calculates branch metrics from each state to each state. A branch metric corresponds to the likelihood of transition from a certain state to a certain state. It is herein assumed that a smaller branch metric indicates a stronger likelihood. Each branch metric A, B, C, D, E can be calculated by the following equations:A=(Yk−14)2;B=(Yk−11)2;C=(Yk−7)2;D=(Yk−3)2; andE=(Yk−0)2.
Herein, A is a branch metric from S5 to S5, B is a branch metric from S2 to S5 and from S5 to S4, C is a branch metric from S1 to S2 and from S4 to S3, D is a branch metric from S0 to S1 and from S3 to S0, and E is a branch metric from S0 to S0.
For example, when the Viterbi detector 7 receives Yk=0, it is determined that the most likely state transition is from S0 to S0. Therefore, the above equations can be rewritten as follows:A=(0−14)2=196;B=(0−11)2=121;C=(0−7)2=49;D=(0−3)2=9; andE=(0−0)2=0.In this case, E has the smallest value. These branch metrics A to E are applied to the ACS operation section 51.
The ACS operation section 51 adds each branch metric and a corresponding path metric in the previous state, and conducts comparison and selection operations. For example, according to the state transition in the trellis diagram of FIG. 9, there are two ways to get to the present state S0: from the previous state S0; and from the previous state S3. The ACS operation section 51 calculates the sum of a path metric LS0k-1 (the sum of the branch metrics from a certain point in the past to the previous state S0) and the current branch metric E, and the sum of a path metric LS3k-1 (the sum of the branch metrics from a certain point in the past to the previous state S3) and the current branch metric D.
The ACS operation section 51 then compares the sums (LS0k-1+E) and (LS3k-1+D) with each other, and selects the smaller (i.e., more likely) one as a path metric of a surviving path. The ACS operation section 51 thus obtains a path metric LS0k in the present state S0, and outputs a path select signal SEL0 to the path memory 52. The path select signal SEL0 is set to “1” when (LS0k-1+E) is smaller than (LS3k-1+D), and set to “0” when (LS0k-1+E) is larger than (LS3k-1+D). In other words, SEL0=1 indicates that the transition from the previous state S0 to the present state S0 was selected as a surviving path, and SEL0=0 indicates that the transition from the previous state S3 to the present state S0 was selected as a surviving path.
There is only one way to get to the present state S1: from the previous state S0. Therefore, the ACS operation section 51 calculates the sum of a path metric LS0k-1 and the current branch metric D as a path metric LS1k in the present state S1. In other words, the ACS operation section 51 does not conduct comparison and selection operations.
For the states S2, S3, S4, S5 as well, the ACS operation section 51 similarly calculates path metrics LS2k, LS3k, LS4k, LS5k in the present state. Regarding the path metric in the present state S5, the ACS operation section 51 outputs a path select signal SEL1 to the path memory 52.
The above operation of the ACS operation section 51 can be represented by the following equations:LS0k=min[LS0k-1+E, LS3k-1+D]; LS1k=LS0k-1+D; LS2k=LS1k-1+C; LS3k=LS4k-1+C; LS4k=LS5k-1+B; LS5k=min[LS2k-1+B, LS5k-1+A]; SEL0=1 (for LS0k-1+E<LS3k-1+D);SEL0=0 (for LS0k-1+E.LS3k-1+D);SEL1=1 (for LS2k-1+B<LS5k-1+A); andSEL1=0 (for LS2k-1+E.LS5k-1+A).
The path memory 52 is a circuit that receives the path select signals SEL0, SEL1 from the ACS operation section 51 and outputs decoded data corresponding to the least recent branch of a surviving path to each state. This operation will now be described with reference to FIGS. 11 to 13B.
FIG. 11 specifically shows the circuit structure of the path memory 52. The path memory 52 of FIG. 11 has registers D arranged in a matrix. Each of the registers D in each row stores the decoded bits corresponding to a surviving path to the respective state.
FIG. 12A shows path metrics at each time and surviving paths at time k=4. It is assumed in FIG. 12A that the Viterbi detector 7 received Yk=(3, 7, 11, 14, 11). A figure(s) in each circle indicates a path metric in a corresponding state at corresponding time. For example, a path metric LS00 in the state S0 at time k=0 is “0” and a path metric LS01 in the state S0 at time k=1 is “32”. Dashed lines in the figure represent the branches that were not selected by the ACS operation section 51. Thin solid lines represent the paths that were not able to be a surviving path at time k=4, and thick solid lines represent the surviving paths in the respective states at time k=4.
FIG. 12B shows decoded bits corresponding to a surviving path to each state at time k=4. For example, a surviving path to the state S0 at time k=4 is S1→S2→S5→S4→S3→S0. Referring to the state transition diagram of FIG. 8, a decoded bit “1” is obtained by the state transition from S1 to S2. Similarly, a decoded bit “1” is obtained by the state transition from S2 to S5, a decoded bit “0” by the state transition from S5 to S4, a decoded bit “0” by the state transition from S4 to S3, and a decoded bit “0” by the state transition from S3 to S0. Therefore, the decoded bits “11000” correspond to the surviving path to the state S0 at time k=4. The decoded bits corresponding to the surviving paths to the states S1, S2, S3, S4, S5 can be similarly obtained as “10001”, “00011”, “11100”, “11110” and “11111”.
FIG. 13A shows path metrics at each time and surviving paths at time k=5. It is assumed in FIG. 13A that the Viterbi detector 7 received Y5=7, that is, Yk=(3, 7, 11, 14, 11, 7). FIG. 13B shows decoded bits corresponding to a surviving path to each state at time k=5.
In the illustrated example, there are two ways to get to the state S0 at time k=5: from the state S0 at time k=4; and from the state S3 at time k=4. The ACS operation section 51 compares the corresponding path metrics, and selects the path from the state S3. Accordingly, the decoded bits corresponding to the surviving path to the state S0 at time k=5 are “111000”, that is, the decoded bits “11100” corresponding to the surviving path to the state S3 at time k=4 plus the decoded bit “0” obtained by the state transition from S3 to S0. For the other states as well, the decoded bit sequences corresponding to the surviving paths to the respective states are similarly obtained by adding a corresponding decoded bit.
The path memory 52 of FIG. 11 conducts the above processing. Note that, in the example of FIG. 11, the registers in the leftmost column respectively store the present decoded bits, and the registers in the rightmost column respectively store the least recent decoded bits, as opposed to the case of FIGS. 12 and 13. It is impossible to implement an infinite path memory length (an infinite number of registers in each row) in the circuitry. In other words, the path memory length has a certain finite value. The path memory 52 therefore outputs the least recent decoded bits in the finite time to the maximum-likelihood determination section 53 as temporary decoded bits B′S0k, B′S1k, B′S2k, B′S3k, B′S4k, B′S5k.
The maximum-likelihood determination section 53 compares the present path metrics of the respective states with each other, and outputs a temporary decoded bit of the state corresponding to the smallest path metric as a decoded bit B′k of the Viterbi detector 7. The maximum-likelihood decoding is originally conducted in this way.
In view of the costs required for comparison between the path metrics of the respective states, maximum-likelihood decoding is sometimes conducted according to the majority logic. More specifically, the number of ones (“1”) in the temporary decoded bits of the respective states is compared with the number of zeros (“0”) therein, and the larger one (“1” or “0”) is output as a decoded bit. In order to further reduce such operation costs, any one of the states may be selected for output as a decoded bit. Of these three methods (original maximum-likelihood decoding, majority logic, and selection of any one of the states), the original maximum-likelihood decoding has the best likelihood, followed by the majority logic and the selection of any one of the state. However, such difference in likelihood often does not cause any practical disadvantage as long as the path memory length is long enough for the Viterbi input signal Yk.
The Viterbi detector having the above structure includes a vast number of registers in the path memory section. This hinders reduction in power consumption and area of the Viterbi detector.
For example, when the above recorded channel bits having the shortest pulse width 3T are equalized by the PR (3, 4, 4, 3) method, the Viterbi detector has six states. Provided that the length for storing the decoded bits corresponding to a surviving path to a certain state, that is, the path memory length, is 40, the Viterbi detector must have 240 (=6 (states)×40 (path memory length)) registers.
In general, the registers consume a larger amount of power and occupy a larger area as compared to the normal logic circuitry. Therefore, reduction in the number of registers is required in order to implement reduction in power consumption and area of the Viterbi detector.